Shortest Path Algorithm：SPFA

发表于   |   分类于   |  

The background is the same as “Shortest Path Algorithm：SPFA” which I compose.I think the story I compose is very vivid, hhhhhhha_

SPFA

SPFA is the abbreviation of Shortest Path First Algorithm.It can deal with graph with negative weight.But when there is a negative circle in graph, SPFA will be incompetent(we can excutive topology program first to avoid this condition when using SPFA).SPFA is a efficent algorithm but its performance is not steady, so we prefer to using Dijkstra for most of time.

We need:

  1. implement a queue and corresponding methods;
  2. an array dis to store the shortest weight to every node;
  3. an array vis to mark whether the node is in queue;

Attentions:

  1. create node 0 as a super source and the weight between it and the node can be source is 0;
  2. there can be more than one path between two nodes and each path may have deffierent weight.
  3. each array needs to be initialized

Core:
dis[x] = min{dis[x], dis[transfer] + m[transfer][x]}
if vis[x] == 0 push(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Title：Dijkstra AC code
// Author： Call偶围城
#include <stdio.h>
#define MAX 1000
#define INF 1000000
int T, S, D;
int dis[MAX+1];
int vis[MAX+1];
int m[MAX+1][MAX+1];
int total;
int queue[MAX+1];
int front;
int tail;
void push(int x) {
	queue[tail] = x;
	tail = (tail+1) % (MAX+1);
}
int pop() {
	int x = queue[front];
	front = (front+1) % (MAX+1);
	return x;
}
int empty() {
	if (front == tail)
		return 1;
	else 
		return 0;
}
void spfa() {
	int transfer;
	int i, j, k;
	while (!empty()) {
		transfer = pop();
		vis[transfer] = 0;
		for (i = 1;i <= total;i++) {
			if (dis[i] > dis[transfer]+m[transfer][i]) {
				dis[i] = dis[transfer] + m[transfer][i];
				if (vis[i] == 0) {
					vis[i] = 1;
					push(i);
				}
			}
		}
	}
}
int main() {
	int i, j, k;
	int a, b, t;
	int min;
	while (scanf("%d%d%d", &T, &S, &D) != EOF) {
		for (i = 0;i <= MAX;i++)
			for (j = 0;j <= MAX;j++)
				m[i][j] = INF;
		total = 0;
		for (i = 0;i < T;i++) {
			scanf("%d%d%d", &a, &b, &t);
			if (a > total) total = a;
			if (b > total) total = b;
			if (m[a][b] > t)
				m[a][b] = m[b][a] = t;
		}
		for (i = 0;i <= MAX;i++)
			vis[i] = 0;
		for (i = 0;i <= MAX;i++)
			dis[i] = INF;
		front = tail = 0;
		for (i = 0;i < S;i++) {
			scanf("%d", &k);
			dis[k] = 0;
			vis[k] = 1;
			push(k);
		}
		spfa();
		min = INF;
		for (i = 0;i < D;i++) {
			scanf("%d", &k);
			if (min > dis[k])
				min = dis[k];
		}
		printf("%d\n", min);
	}
	return 0;
}